This invention relates to a method for rendering color images. More specifically, this invention relates to a method for half-toning color images in situations where a limited set of primary colors are available, and this limited set may not be well structured. The method of the present invention is particularly, although not exclusively, intended for use with color electrophoretic displays
Half-toning has been used for many decades in the printing industry to represent gray tones by covering a varying proportion of each pixel of white paper with black ink. Similar half-toning schemes can be used with CMY or CMYK color printing systems, with the color channels being varied independently of each other.
However, there are many color systems in which the color channels cannot be varied independently of one another, in as much as each pixel can display any one of a limited set of primary colors (such systems may hereinafter be referred to as “limited palette displays” or “LPD's”); the ECD patent color displays are of this type. To create other colors, the primaries must be spatially dithered to produce the correct color sensation. It is known to effect such spatial dithering by using, for any desired color, only the primary colors at the vertices of a tetrahedron which contains the desired color; see, for example:                Arad, N., Shaked, D., Baharav, Z., & Lin, Q. (1999). Barycentric Screening and        Ostromoukhov, Victor, and Roger D. Hersch. “Multi-color and artistic dithering.” Proceedings of the 26th annual conference on Computer graphics and interactive techniques. ACM Press/Addison-Wesley Publishing Co., 1999.Both these documents effect dithering by means of a threshold-array based screening method, which is a simple dithering method that has been found not to give good results in ECD patent displays.        
Standard dithering algorithms such as error diffusion algorithms (in which the “error” introduced by printing one pixel in a particular color which differs from the color theoretically required at that pixel is distributed among neighboring pixels so that overall the correct color sensation is produced) can be employed with limited palette displays. However, such standard algorithms are typically intended for use with a limited palette which is “well structured”, in the sense that the distances in the appropriate color space between the primary colors are substantially constant. There is considerable literature on the problems of designing optimal color palettes that perform well with error diffusion; see, for example:                Kolpatzik, Bernd W., and Charles A. Bouman. “Optimized Universal Color Palette Design for Error Diffusion.” Journal of Electronic Imaging 4.2 (1995): 131-143.However, in ECD and similar limited palette displays, in which the limited palette is defined by the colors capable of being generated by the system, the limited palette may not be well structured, i.e., the distances between the various primaries in the color space may differ greatly from one another.        
FIG. 1 of the accompanying drawings is a schematic flow diagram of a prior art palette based error diffusion method, generally designated 100. At input 102, color values xi,j are fed to a processor 104, where they are added to the output of an error filter 106 (described below) to produce a modified input ui,j. The modified inputs ui,j are fed to a quantizer 108, which also receives details of the palette {Pk} of the output device. The quantizer 108 determines the appropriate color for the pixel being considered, given by:
      y          i      ,      j        =            argmin              P        k              ⁢                                  u                      i            ,            j                          -                  P          k                          and feeds to appropriate colors to the device controller (or stores the color values for later transmission to the device controller). Both the modified inputs ui,j and the outputs yi,j are fed to a processor 110, which calculates error values ei,j, where:ei,j=ui,j−yi,j The error values ei,j are then fed to the error filter 106, which serves to distribute the error values over one or more selected pixels. For example, if the error diffusion is being carried out on pixels from left to right in each row and from top to bottom in the image, the error filter 106 might distribute the error over the next pixel in the row being processed, and the three nearest neighbors of the pixel being processed in the next row down. Alternatively, the error filter 106 might distribute the error over the next two pixels in the row being processed, and the nearest neighbors of the pixel being processed in the next two rows down. It will be appreciated that the error filter need not apply the same proportion of the error to each of the pixels over which the error is distributed; for example when the error filter 106 distributes the error over the next pixel in the row being processed, and the three nearest neighbors of the pixel being processed in the next row down, it may be appropriate to distribute more of the error to the next pixel in the row being processed and to the pixel immediately below the pixel being processed, and less of the error to the two diagonal neighbors of the pixel being processed.
Unfortunately, it has been found that if one attempts to use conventional error diffusion methods such as that shown in FIG. 1 to ECD and similar limited palette displays, severe artifacts are generated which may render the resultant images unusable. For example, in one type of artifact, (hereinafter called a “transient” artifact) when stepping from one input color to a next very different color, the spatial transient can be so long that the output never settles to the correct average even across the size of object being rendered. In another type of artifact (hereinafter called a “pattern jumping” artifact), for a constant color input image, the output jumps between two different sets of primaries at a seemingly random position in the image. Although both sets of primaries should ideally produce output close to the color being requested, the resultant output is not robust because small changes in the system can cause these switching between the two sets and the texture change at such a jump is also noticeable and unpleasant.
The present invention seeks to provide a method of rendering color images which can be used with palettes which are not well structured, and may be large, without producing transient and pattern jumping artifacts to which standard error diffusion methods are susceptible.